package com.wenhao.leetcode.medium;

/**
 * 题目：https://leetcode-cn.com/problems/word-search/
 * 单词搜索
 *
 *
 * @author Wenhao Tong
 * @create 2021-06-28 16:39
 */
public class LeetCode79 {

    public static void main(String[] args) {
        LeetCode79 leetCode79 = new LeetCode79();
        boolean aaa = leetCode79.exist(new char[][]{{'a', 'a'}}, "aaa");
        System.out.println(aaa);
    }


    public boolean exist(char[][] board, String word) {
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0;i < board.length;i++) {
            for (int j = 0;j < board[i].length;j++) {
                if (dfs(i,j,word,0,board,visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs (int i,int j,String word,int start,char[][] board,boolean[][] visited) {
        if (word.charAt(start) == board[i][j]) {
//            List<int[]> next = getNext(i, j, visited);
            if (start == word.length() - 1) {
                return true;
            }

            visited[i][j] = true;
//            for (int[] coor : next) {
//                if (dfs(coor[0],coor[1],word,start + 1,board,visited)) {
//                    return true;
//                }
//            }
            // 写在一个方法里面，效率高一点
            if (i + 1 < visited.length && !visited[i + 1][j] && dfs(i + 1,j,word,start + 1,board,visited)) {
                return true;
            }
            if (j + 1 < visited[i].length && !visited[i][j + 1] && dfs(i,j + 1,word,start + 1,board,visited)){
                return true;
            }
            if (i - 1 > -1 && !visited[i - 1][j] && dfs(i - 1,j,word,start + 1,board,visited)) {
                return true;
            }
            if (j - 1 > -1 && !visited[i][j - 1] && dfs(i,j - 1,word,start + 1,board,visited)) {
                return true;
            }
            visited[i][j] = false;
        }
        return false;
    }

//    private List<int[]> getNext(int i,int j,boolean[][] visited) {
//        List<int[]> next = new ArrayList<>();
//        if (i + 1 < visited.length && !visited[i + 1][j]) {
//            next.add(new int[]{i + 1,j});
//        }
//        if (j + 1 < visited[i].length && !visited[i][j + 1]) {
//            next.add(new int[]{i,j + 1});
//        }
//        if (i - 1 > -1 && !visited[i - 1][j]) {
//            next.add(new int[]{i - 1,j});
//        }
//        if (j - 1 > -1 && !visited[i][j - 1]) {
//            next.add(new int[]{i,j - 1});
//        }
//        return next;
//    }


}
